// 90.子集
// https://leetcode.cn/problems/subsets-ii/
// DFS 去重

/**
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

 */

class HashMap {
    constructor(digitArr) {
        this.tree = {};
        this.keyIsNumber = true;

        digitArr.forEach((ele) => {
            this.add(ele);
        });
    }

    add(key, value = null) {
        if (this.tree.hasOwnProperty(key)) {
            this.tree[key] += 1;
        } else {
            this.tree[key] = 1;
        }
    }

    flat() {
        let arr = Object.keys(this.tree);
        let ret = arr.map((ele) => [parseInt(ele), this.tree[ele]]);

        ret[ret.length - 1].push(ret[ret.length - 1][1]);
        for (let j = ret.length - 2; j >= 0; j--) {
            ret[j].push(ret[j][1] + ret[j + 1][2]);
        }
        return ret;
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    let hashmap = new HashMap(nums);
    let flatArr = hashmap.flat();
    console.log(JSON.stringify(flatArr));

    let ret = [[]];
    for (let i = 1; i <= nums.length; i++) {
        for (let j = 0; j < flatArr.length; j++) {
            if (flatArr[j][2] < i) break;
            dfs(flatArr, j, 0, i, [], ret);
        }
    }

    console.log(JSON.stringify(ret));
    return ret;
};

function dfs(remainArr, headIndex, curCount, maxCount, curArr, all) {
    if (curCount === maxCount) {
        all.push(curArr);
        return;
    }

    let cur_val = remainArr[headIndex];
    let new_remain = JSON.parse(JSON.stringify(remainArr));
    if (new_remain[headIndex][1] <= 1) {
        new_remain.splice(headIndex, 1);
    } else {
        new_remain[headIndex][1] = new_remain[headIndex][1] - 1;
    }
    curArr.push(cur_val[0]);
    if (curArr.length === maxCount) {
        all.push(curArr);
        return;
    }

    for (let i = headIndex; i < new_remain.length; i++) {
        dfs(new_remain, i, curArr.length, maxCount, [].concat(curArr), all);
    }
}

// subsetsWithDup([1, 2, 2]);
// subsetsWithDup([0]);
// [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
subsetsWithDup([1, 2, 3]);
